package com.example.algorithm.dp;

/**
 * ProjectName personal-algorithm
 * 不同路径2
 * @author xieyucan
 * <br>CreateDate 2022/9/7 12:31
 */
public class DifferentPathPlus {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int hang=obstacleGrid.length;
        int lie=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        int [][]dp=new int[hang][lie];
        for(int i=0;i<lie;i++)
        {
            if(obstacleGrid[0][i]==1)
            {
                for(int j=i;j<lie;j++)
                {
                    dp[0][j]=0;
                }
                break;
            }
            dp[0][i]=1;
        }
        for(int i=0;i<hang;i++)
        {
            if(obstacleGrid[i][0]==1)
            {
                for(int j=i;j<hang;j++)
                {
                    dp[j][0]=0;
                }
                break;
            }
            dp[i][0]=1;
        }
        for(int i=1;i<hang;i++)
        {
            for(int j=1;j<lie;j++)
            {
                if(obstacleGrid[i][j]==1)
                {
                    dp[i][j]=0;
                }else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[hang-1][lie-1];
    }

    public static void main(String[] args) {
        DifferentPathPlus differentPathPlus = new DifferentPathPlus();
        int [][]can={{0,0,0},{0,1,0},{0,0,0}};
        System.out.println(differentPathPlus.uniquePathsWithObstacles(can));
    }
}
